package leetcode.code0688;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：4 ms, 在所有 Java 提交中击败了92.23%的用户
//
//内存消耗：41 MB, 在所有 Java 提交中击败了5.51%的用户
//
//通过测试用例：22 / 22
public class Solution2 implements IDebug {

	int[] d = new int[] { -1, -2, -2, -1, -2, 1, -1, 2, 1, 2, 2, 1, 2, -1, 1, -2 };

	int n;

	public double knightProbability(int n, int k, int row, int column) {
		this.n = n;
		Double[][] dp = new Double[k + 1][n * n];
		return this.f(row, column, k, dp) / Math.pow(8, k);
	}

	private double f(int row, int column, int k, Double[][] dp) {
		if (k == 0) {
			return 1;
		}
		if (dp[k][row * n + column] != null) {
			return dp[k][row * n + column];
		}
		double ans = 0;
		for (int i = 0; i < 16; i += 2) {
			int x = row + d[i], y = column + d[i + 1];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				ans += this.f(x, y, k - 1, dp);
			}
		}
		dp[k][row * n + column] = ans;
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.knightProbability(8, 30, 6, 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
